package com.cqs.leetcode.ds;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by cqs on 2018/3/24.
 */
public class Trie {

    private Node root = new Node(null, 0);

    public Node getRoot() {
        return root;
    }

    //
    public class Node {
        //
        private Character aChar;
        private int value;
        //
        private Map<Character, Node> children = new HashMap<>();

        public Node(Character aChar, int value) {
            this.aChar = aChar;
            this.value = value;
        }

        public Map<Character, Node> getChildren() {
            return children;
        }
    }

    public void insert(String str) {
        if (str != null) {
            Node node = root;
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                node = insert(node, ch);
            }
        }
    }

    public boolean exists(String str) {
        if (str == null || str.equals("")) return false;
        Node node = root;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if ((node = node.children.get(ch)) == null) {
                return false;
            }
        }
        return true;
    }


    private Node insert(Node node, char ca) {
        Node cn = node.children.get(ca);
        if (cn == null) {
            cn = new Node(ca, 1);
            node.children.put(ca,cn);
        }
        return cn;
    }


    public static void main(String[] args) {
        Trie trie = new Trie();
        String ss = "hello world";
        trie.insert(ss);
        System.out.println(trie.exists(ss));

    }

}
